package Ep06_BinaryTree.BT18_0106;

import Ep06_BinaryTree.TreeNode;

import java.util.Arrays;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/5/30 12:55        自己写的，性能好差，可能的原因是每次递归中存在5次遍历
 * 说明：lc 0106 根据中序和后序构造二叉树
 *
 * 题目：
 *      给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树
 *
 * 示例：
 *      输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
 *      输出：[3,9,20,null,null,15,7]
 *
 * 中序： 左 中 右
 * 后序： 左 右 中
 *
 * 因此后序的最后一位一定是二叉树的根节点
 */

public class Mine {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) return null;
        int rootValue = postorder[postorder.length -1];
        TreeNode root = new TreeNode(rootValue);
        // 如果后序只剩最后一位，就说明到了叶子结点，直接return即可
        if (inorder.length == 1) return root;
        int index = 0;
        // 这里取得中序数组中根节点的分割位置
        for (index = 0; index < inorder.length; index++) {
            if (inorder[index] == rootValue) break;
        }
        System.out.println("index = " + index);
        // 切割中序数组
        int[] subInArrayL = new int[index];
        for (int i = 0; i < index; i++) {
            subInArrayL[i] = inorder[i];
        }
        int[] subInArrayR = new int[inorder.length - 1 - index];
        for (int i = 0; i < inorder.length - index - 1; i++) {
            subInArrayR[i] = inorder[index + i + 1];
        }
        System.out.println("subInArrayL: " + Arrays.toString(subInArrayL));
        System.out.println("subInArrayR: " + Arrays.toString(subInArrayR));

        // 切割后序数组
        int[] subPostArrayL = new int[index];
        for (int i = 0; i < index; i++) {
            subPostArrayL[i] = postorder[i];
        }
        int[] subPostArrayR = new int[inorder.length - 1 - index];
        for (int i = 0; i < inorder.length - index - 1; i++) {
            subPostArrayR[i] = postorder[i + subPostArrayL.length];
        }
        System.out.println("subPostArrayL: " + Arrays.toString(subPostArrayL));
        System.out.println("subPostArrayR: " + Arrays.toString(subPostArrayR));

        // 递归
        root.left = buildTree(subInArrayL, subPostArrayL);
        root.right = buildTree(subInArrayR, subPostArrayR);
        return root;
    }

}
